package problem130;

//130.被围绕的区域
//https://leetcode.cn/problems/surrounded-regions/description/

class Solution {
    int n,m;
    boolean[][] st;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    public void solve(char[][] board) {
        n = board.length;
        m = board[0].length;
        st = new boolean[n][m];
        for(int i = 0; i<n; i++) {
            if(board[i][0] == 'O') {
                dfs(board, i, 0, 'O');
            }
            if(board[i][m-1] == 'O') {
                dfs(board, i, m-1, 'O');
            }
        }

        for(int j = 0; j<m; j++) {
            if(board[0][j] == 'O') {
                dfs(board, 0, j, 'O');
            }
            if(board[n-1][j] == 'O') {
                dfs(board, n-1, j, 'O');
            }
        }

        for(int i = 1; i<n-1; i++) {
            for(int j = 1; j<m-1; j++) {
                if(board[i][j] == 'O' && !st[i][j]) {
                    dfs(board, i, j, 'X');
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y, char ch) {
        st[x][y] = true;
        board[x][y] = ch;
        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && board[dx][dy] == 'O' && !st[dx][dy]) {
                dfs(board, dx, dy, ch);
            }
        }
    }
}